The present application relates to systems and methods for signal acquisition and recovery, and more particularly to techniques for adaptive data acquisition.
For many weak signals, noise can overwhelm the important information. There are various procedures for extracting a signal (image, spatial or temporal waveform, etc.) from noise.
Consider the following canonical signal model,Xi˜N(μi,1), i=1, . . . ,n,  (1)where N(μi, 1) denotes the normal distribution with mean μi and unit variance. The signal μ=(μ1, . . . , μn) is sparse if most of the components μi are zero. Identifying the locations of the non-zero components based on the data X=(X1, . . . , Xn) when n is very large is a fundamental problem arising in many applications. A common approach in these problems entails coordinate-wise thresholding of the observed data X at a given level, identifying the locations whose corresponding observation exceeds the threshold as signal components.
Among such methods, false-discovery rate (FDR) analysis, described e.g., in Benjamini et al. (1995), Controlling the false discovery rate: a practical and powerful approach to multiple testing, J. R. Statist. Soc. B, 57, 289-300, has been used because it is less conservative than Bonferroni correction, and because it enjoys asymptotically optimal performance characteristics. Suppose that the number of non-zero components of μ grows sublinearly in n according to n1-β for β∈(0, 1), and that each non-zero component takes the same (positive) value √{square root over (2r log n)} for r>0. For a given recovery procedure, the false-discovery proportion (FDP) can be defined to be the number of falsely discovered components relative to the total number of discoveries, and the non-discovery proportion (NDP) to be the number of non-zero components missed relative to the total number of non-zero components. The asymptotic limits of sparse recovery for data collected according to equation (1) are sharply delineated in the (β, r) parameter space. Specifically, if r<β, no recovery procedure based on coordinate-wise thresholding of the observed data can drive the FDP and NDP to zero as n→∞. But, when r>β, there exists a recovery procedure based on coordinate-wise thresholding that drives both the NDP and FDP to zero as n→∞. Thus, the relation r=β defines a sharp asymptotic boundary in the parameter space, identifying when sparse signals observed under equation (1) can be reliably recovered.
Suppose that a n×1 signal μ in noise is observed according to equation (1). The signal μ is assumed to be sparse—that is, most of the components of the signal are equal to zero. S can be defined as S={i: μi≠0, i=1, . . . , n}. The elements of S are called the signal components, and the elements in the complement set, Sc={1, . . . , n}\S, are called null components. The goal of a signal recovery procedure is to identify the signal components (in other words, estimate S) using the observed data X. Let Ŝ(X) be the outcome of a given signal recovery procedure. The false-discovery proportion (FDP) can then be defined to be the ratio between the number of falsely-discovered signal components and the total number of discovered components, FDP=|Ŝ(X)\S|/|Ŝ(X)|, and the non-discovery proportion defined to be the ratio between the number of undiscovered signal components and the total number of signal components, NDP=|S\Ŝ(X)|/|S|. An effective signal recovery procedure controls both the FDP and NDP.
Consider sparse signals having n1-β signal components each of amplitude √{square root over (2r log n)}, for some β∈(0, 1) and r>0, under equation (1). A coordinate-wise thresholding procedure.S(X)={i:Xi>τ}, τ>0,  (2)can be used to estimate the locations of the signal components. It follows that if r>β, equation (2), with a threshold τ that may depend on r, β, and n, drives both the FDP and NDP to zero with probability one as n→∞. Conversely, if r<β, then no such coordinate-wise thresholding procedure can drive the FDP and NDP to zero simultaneously with probability tending to one as n→∞. In other words, for the specified signal parameterization and observation model, the (β, r) parameter plane is partitioned into two disjoint regions. In the region r>β, sparse signal components can be reliably located using a coordinate-wise thresholding procedure. In the complementary region where r<β, no coordinate-wise thresholding procedure is reliable in the sense of controlling both the FDP and NDP. This establishes a sharp boundary in the parameter space, r=β, for large-sample consistent recovery of sparse signals.
In adaptive measurement procedures, the location or method of future measurements or experiments depends (in a strict statistical sense) on the outcomes of prior and present measurements. In contrast, procedures where the measurement process or set of experiments can be specified completely before any data are collected (procedures that do not utilize feedback to guide future measurements or experiments) are called non-adaptive procedures. Adaptive measurement can succeed at recovering signals that are otherwise unrecoverable using passive methods because the signals are either too weakly expressed or have too few relevant signal components.